package editor.cn;

import javax.swing.plaf.nimbus.NimbusLookAndFeel;

class Solution300{
    public static void main(String[] args) {
        Solution solution = new Solution300().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLIS(int[] nums) {
    //方法1：dp
        return dp(nums);
    }

    private int dp(int[] nums) {
            int n= nums.length;
            int ans=1;//这里是因为至少有1个串(即为char)！
            int[] dp = new int[n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i]>nums[j]){
                        dp[i]=Math.max(dp[i],dp[j]);//这里可以从后往前思考，是不断地将前面小于num[i]的数num[j]加在他的前面
                    }
                }
                ans=Math.max(ans,++dp[i]);//不断地更新每次求解后的dp，这是在前面求出的dp[i]本身的num[i]这一个数字加上前面的dp[i].所以会有++dp[i]
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}











